Computer Science Gate 2017 Set 1 Questions

Research in the workplace reveals that people work for many reasons _________.

a) money beside
b) beside money
c) money besides
d) besides money

Find the smallest number y such that y*162 is a perfect cube.

a) 24
b) 27
c) 32
d) 36

Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the colour white. Gulab and Neel like all the colours. In how many different ways can they choose the shirts so that no one has a shirt with a colour he or she dislikes?

a) 21
b) 18
c) 16
d) 14

The expression [ (x + y) - |x - y| ] / 2 is equal to___

a) 1
b) the minimum of x and y
c) the maximum of x and y
d) none of the above

a) Nationalists are highly imaginative.
b) Nationalists are highly imaginative.
c) Our colonial past never happened.
d) Our colonial past never happened.

Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her immediate right. None of the women are right-handed. The number of women at the table is

a) 2
b) 3
c) 4
d) Can not be determined

After Rajendra Chola returned from his voyage to Indonesia, he ______ to visit the temple in Tanjavur.

a) was wishing
b) is wishing
c) wished
d) had wished

The probability that a k-digit number does NOT contain the digits 0, 5 or 9 is__

a) 0.3^k
b) 0.6^k
c) 0.7^k
d) 0.9^k

Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul. Which of the following pairs are seated opposite each other ?

a) Rahul and Murali
b) Srinivas and Arul
c) Srinivas and Murali
d) Srinivas and Rahul

Consider the following grammar:

Consider the language L given by the regular expression (a + b)*b(a +b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ______.

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* .We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denotes the language {x#f(x)|x∈A*}. Which of the following statements is true?

a) f if computable if and only if Lf is recursive.
b) f if computable if and only if Lf is recursive enumerable.
c) if f is computable then Lf is recursive, but not conversely.
d) if f is computable then Lf is recursively enumerable, but not conversely.

Consider the following languages over the alphabet ∑= {a,b,c}.
Let L1 ={aⁿbⁿc^m | m, n >= 0 } and
L2 = {a^mbⁿcⁿ| m, n >= 0}.

Which of the following are context-free languages ?
I. L₁ ∪ L₂
II. L₁ ∩ L₂

a) I only
b) II only
c) I and II
d) Neither I nor II

If G is grammar with productions

a) abab
b) aaab
c) abbaa
d) babba

Consider the following grammar over the alphabet {a,b,c} given below, S and T are non-terminals.

a) Finite
b) Non-finite but regular
c) Context-free but not regular
d) Recursive but not context-free

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:

a) {(ab)ⁿ(cb)ⁿ | n >= 1 }
b) {(abⁿcb^m₁cb^m₂...cb^m_n | n, m1, m2, ....., mn >= 1 }
c) {(ab)ⁿ(cb^m)ⁿ | n >= 1 }
d) {(ab)ⁿ(cbⁿ)^m | m, n >= 1 }

Consider the following grammar

a) {R}
b) {w}
c) {w, y}
d) {w, ∉}

The output of executing the following C program is ________.

Consider the following C program.

Consider the following two functions
void fun1(int n){
    if(n == 0) return;
      printf(“%d”, n);
    fun2(n-2);
    printf(“%d”, n);
}

void fun2(int n){
    if(n == 0) return;
      printf(“%d”, n);
      fun1(++n);
      printf(“%d”, n);
}

The output printed when fun1 (5) is called is

a) 53423122233445
b) 53423120112233
c) 53423122132435
d) 53423120213243

Consider the C functions foo and bar given below:

a) Return of 6 and 6 respectively.
b) Infinite loop and abnormal termination respectively.
c) Abnomal termination and infinite loop respectively.
d) Both terminating abnormally.

Consider the C code fragment given below.

a) append list m to the end of list n for all inputs
b) either cause a null pointer dereference or append list m to the end of list n
c) cause a null pointer dereference for all inputs.
d) append list n to the end of list m for all inputs.

Consider the C code fragment given below.

a) append list m to the end of list n for all inputs
b) either cause a null pointer dereference or append list m to the end of list n
c) cause a null pointer dereference for all inputs.
d) append list n to the end of list m for all inputs.

Consider the following C code:

a) compiler error as the return of malloc is not typecast appropriately.
b) compiler error because the comparison should be made as x==NULL and not as shown.
c) compiles successfully but execution may result in dangling pointer.
d) compiles successfully but execution may result in memory leak.

Consider the C struct defines below:

a) Post-increment addressing mode. (R1)+
b) Pre-decrement addressing mode, -(R1)
c) Register direct addressing mode, R1
d) Index addressing mode, X(R1), where X is an offset represented in 2’s complement 16-bit representation.

Instruction execution in a processor is divided into 5 stages.
Instruction Fetch(IF), Instruction Decode (ID), Operand Fetch(OF), Execute(EX), and Write Back(WB),
These stages take 5,4,20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementations of the processor are contemplated:

(i) a naïve pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage id divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.


The speedup (correct to two decimals places) achieved by EP over NP in executing 20 independent instructions with no hazards is ________________.

A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ______ bits.

Consider a 2-way set associative cache with 256 blocks and uses LRU replacement, Initially the cache is empty. Conflict misses are those misses which occur due the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks

Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC- relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to the address of the next instruction in the program sequence. Consider the following instruction sequence

Consider the expression (a-1) * ((( b + c ) / 3 )) + d)). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which

(i) only load and store instructions can have memory operands and
(ii) arithmetic instructions can have only register or immediate operands The value of X is ________.

The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n - f. The range of decimal values for X in this representation is

a) 2^-f
b) 2^-f to ( 2ⁱ-2^-f)
c) 0 to 2^-i
d) 0 to (2ⁱ - 2^-f)

The values of parameters for the Stop-and – Wait ARQ protocol are as given below.

In a RSA cryptosystem a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of A is 35. Then the private key of A is ____________.

Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segment is sent to the TCP server. Server-side TCP responds by sending an ACK which is received by the client-side TCP. As per the TCP connection state diagram(RFC 793), in which state does the client side TCP connection wait for the FIN from the server-side TCP?

a) LAST-ACK
b) TIME-WAIT
c) FIN-WAIT-1
d) FIN-WAIT-2

A computer network uses polynomial over GF(2) for error checking with 8 bits as information bits and uses x³ + x + 1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as

a) 01011011010
b) 01011011011
c) 01011011101
d) 01011011100

A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place.

a) (I) only
b) (II) only
c) (I) and (II) only
d) (II) and (III) only

Consider the following table

a) P-(ii), Q-(iii), R-(i)
b) P-(iii), Q-(i), R-(ii)
c) P-(ii), Q-(i), R-(iii)
d) P-(i), Q-(ii), R-(iii)

Consider the following functions from positives integers to real numbers

10, √n, n, log₂n, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

a) log₂n, 100/n,10, √n, n,
b) 100/n,10,log₂n, √n, n,
c) 10,100/n, √n,log₂n,n
d) 100/n,log₂n, 10,√n, n,

Consider the following intermediate program in three address code

a) p₁ = a - b
q₁ =p₁ * c
p₁= u * v
q₁ =p₁ + q₁

b) p₃= a - b
q₄= p₃* c
p₄= u * v
q₅ =p₄+ q₄

c) p₁ = a - b
q₁=p₂ * c
p₃= u * v
q₂= p₄ + q₃

d) p₁ = a - b
q₁= p * c
p₂= u * v
q₂= p + q

Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________.

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:

a) I only
b) II only
c) both I and II
d) neither I and II

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.

a) 4 and 15 respectively
b) 3 and 14 respectively
c) 4 and 14 respectively
d) 3 and 15 respectively

In a database system, unique time stamps are assigned to each transaction using Lamport’s logical clock. Let TS(T1) and TS(T2) be the time stamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database assuming that a killed transaction is restarted with the same timestamp.

a) The database system is both deadlock-free and starvation- free.
b) The database system is deadlock- free, but not starvation-free.
c) The database system is starvation-free but not deadlock- free.
d) The database system is neither deadlock- free nor starvation-free.

Consider a database that has the relation schemas EMP (EmpId, EmpName, DepId), and DEPT(DeptName, DeptId). Note that the DepId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

a) I and II only
b) I and III only
c) II and III only
d) I, II, and III

The following functional dependencies hold true for the relational schema R{V, W, X, Y, Z}:

a) V→W
V→X
Y→V
Y→Z

b) V→W
W→X
Y→V
Y→Z

c) V→W
V→X
Y→V
Y→X
Y→Z

d) V→W
W→X
Y→V
Y→X
Y→Z

When two 8-bit numbers A₇ ... A₀ and B₇ ... B₀ in 2^^s complement representation (with A₀ and B₀ as the least significant bits) are added using ripple-carry adder. the sum bits obtained are S₇ ... S₀ and the carry bits are C₇ ... C₀. An overflow is said to have occurred if

a) the carry bit C₇ is 1
b) all the carry bits (C₇, ... , C₀ ) are 1
c) (A₇ . B₇ . S₇' + A₇' . B₇' . S₇) is 1
d) (A₀ . B₀ . S₀' + A₀' . B₀' . S₀) is 1

Let p, q, and r be the propositions and the expression (p -> q) -> r be a contradiction. Then, the expression (r -> p)-> q is

a) a tautology
b) a contradiction
c) always TRUE when p is FALSE
d) always TRUE when q is TRUE

Consider the first-order logic sentence

a) II only
b) IV only
c) I and IV only
d) II and III only

The statement (¬ p) → (¬ q) is logically equivalent to which of the statements below?


I. p → q
II. q → p
III. (¬ q) ∨ p
IV. (¬ p) ∨ q

a) I only
b) II only
c) I and IV only
d) II and III only

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.

Let u and v be two vectors in R² whose Euclidean norms satisfy ||u|| = 2||v||. What is the value α such that w = u + αv bisects the angle between u and v ?

a) 2
b) 1
c) 1/2
d) -1/2

Let X be a Gaussian random variable with mean 0 and variance σ². Let Y = max(X,0) where max(a,b) is the maximum of a and b. The median of Y is _____.

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:

Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of allocated frames increases. Now consider the following statements:

a) S1 is true, S2 is true
b) S1 is true, S2 is false
c) S1 is false , S2 is true
d) S1 is false, S2 is false

A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

a) x = 1, y = 2
b) x = 2, y = 1
c) x = 2, y = 2
d) x = 1, y = 1

Threads of a process share

a) global variables but not heap
b) heap but not global variables.
c) neither global variables nor heap.
d) both heap and global variables.